package com.gitee.wsl.time.wheel

import com.gitee.wsl.mathematics.function.frequency.ceilingPowerOfTwo
import kotlin.math.max
import kotlin.math.min


/**
 * A probabilistic multiset for estimating the popularity of an element within a time window. The
 * maximum frequency of an element is limited to 15 (4-bits) and an aging process periodically
 * halves the popularity of all elements.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 *
 * 这个类的实现采用了 Count-Min Sketch 数据结构，
 * 它维护了一个 long[] table 一维数组，每个元素有 64 位，每 4 位作为一个计数器（这也就限定了最大频率为 15），
 * 那么数组中每个槽位便是 16 个计数器。通过哈希函数取 4 个独立的计数值，将其中的最小值作为元素的访问频率。
 * table 的初始大小为缓存最大容量最接近的 2 的 n 次幂，并在计算哈希值时使用 blockMask 掩码来使哈希结果均匀分布，
 * 保证了获取元素访问频率的正确率为 93.75%，达到空间与时间的平衡。
 * 它的实现原理和布隆过滤器类似，牺牲了部分准确性，但减少了占用内存的大小
 */
internal class FrequencySketch<E>
/**
 * Creates a lazily initialized frequency sketch, requiring [.ensureCapacity] be called
 * when the maximum size of the cache has been determined.
 */
{
    var sampleSize: Int = 0
    var blockMask: Int = 0
    var table: LongArray?
        get() {
            TODO()
        }
        set(value) {}
    var size: Int = 0

    /**
     * Initializes and increases the capacity of this `FrequencySketch` instance, if necessary,
     * to ensure that it can accurately estimate the popularity of elements given the maximum size of
     * the cache. This operation forgets all previous counts when resizing.
     *
     * @param maximumSize the maximum size of the cache
     */
    fun ensureCapacity(maximumSize: Long) {
        require(maximumSize >= 0)
        val maximum = min(maximumSize, (Int.Companion.MAX_VALUE ushr 1).toLong()).toInt()
        if ((table != null) && (table!!.size >= maximum)) {
            return
        }

        table = LongArray(max(ceilingPowerOfTwo(maximum), 8))
        sampleSize = if (maximumSize == 0L) 10 else (10 * maximum)
        blockMask = (table!!.size ushr 3) - 1
        if (sampleSize <= 0) {
            sampleSize = Int.Companion.MAX_VALUE
        }
        size = 0
    }

    val isNotInitialized: Boolean
        /**
         * Returns if the sketch has not yet been initialized, requiring that [.ensureCapacity] is
         * called before it begins to track frequencies.
         */
        get() = (table == null)

    /**
     * Returns the estimated number of occurrences of an element, up to the maximum (15).
     *
     * @param e the element to count occurrences of
     * @return the estimated number of occurrences of the element; possibly zero but never negative
     */
    fun frequency(e: E?): Int {
        if (this.isNotInitialized) {
            return 0
        }

        var frequency = Int.Companion.MAX_VALUE
        val blockHash = spread(e.hashCode())
        val counterHash = rehash(blockHash)
        val block = (blockHash and blockMask) shl 3
        for (i in 0..3) {
            val h = counterHash ushr (i shl 3)
            val index = (h ushr 1) and 15
            val offset = h and 1
            val slot = block + offset + (i shl 1)
            val count = ((table!![slot] ushr (index shl 2)) and 0xfL).toInt()
            frequency = min(frequency, count)
        }
        return frequency
    }

    /**
     * Increments the popularity of the element if it does not exceed the maximum (15). The popularity
     * of all elements will be periodically down sampled when the observed events exceed a threshold.
     * This process provides a frequency aging to allow expired long term entries to fade away.
     *
     * @param e the element to add
     */
    fun increment(e: E?) {
        if (this.isNotInitialized) {
            return
        }

        val blockHash = spread(e.hashCode())
        val counterHash = rehash(blockHash)
        val block = (blockHash and blockMask) shl 3

        // Loop unrolling improves throughput by 10m ops/s
        val h0 = counterHash
        val h1 = counterHash ushr 8
        val h2 = counterHash ushr 16
        val h3 = counterHash ushr 24

        val index0 = (h0 ushr 1) and 15
        val index1 = (h1 ushr 1) and 15
        val index2 = (h2 ushr 1) and 15
        val index3 = (h3 ushr 1) and 15

        val slot0 = block + (h0 and 1)
        val slot1 = block + (h1 and 1) + 2
        val slot2 = block + (h2 and 1) + 4
        val slot3 = block + (h3 and 1) + 6

        val added =
            (incrementAt(slot0, index0)
                    or incrementAt(slot1, index1)
                    or incrementAt(slot2, index2)
                    or incrementAt(slot3, index3))

        if (added && (++size == sampleSize)) {
            reset()
        }
    }

    /**
     * Increments the specified counter by 1 if it is not already at the maximum value (15).
     *
     * @param i the table index (16 counters)
     * @param j the counter to increment
     * @return if incremented
     */
    fun incrementAt(i: Int, j: Int): Boolean {
        val offset = j shl 2
        val mask = (0xfL shl offset)
        if ((table!![i] and mask) != mask) {
            table!![i] += (1L shl offset)
            return true
        }
        return false
    }

    /** Reduces every counter by half of its original value.  */
    fun reset() {
         var count = 0
        for (i in table!!.indices) {
            //count += java.lang.Long.bitCount(table!![i] and ONE_MASK)
            count += (table!![i] and ONE_MASK).countOneBits()
            table!![i] = (table!![i] ushr 1) and RESET_MASK
        }
        size = (size - (count ushr 2)) ushr 1
    }

    companion object {
        /*
   * This class maintains a 4-bit CountMinSketch [1] with periodic aging to provide the popularity
   * history for the TinyLfu admission policy [2]. The time and space efficiency of the sketch
   * allows it to cheaply estimate the frequency of an entry in a stream of cache access events.
   *
   * The counter matrix is represented as a single-dimensional array holding 16 counters per slot. A
   * fixed depth of four balances the accuracy and cost, resulting in a width of four times the
   * length of the array. To retain an accurate estimation, the array's length equals the maximum
   * number of entries in the cache, increased to the closest power-of-two to exploit more efficient
   * bit masking. This configuration results in a confidence of 93.75% and an error bound of
   * e / width.
   *
   * To improve hardware efficiency, an item's counters are constrained to a 64-byte block, which is
   * the size of an L1 cache line. This differs from the theoretical ideal where counters are
   * uniformly distributed to minimize collisions. In that configuration, the memory accesses are
   * not predictable and lack spatial locality, which may cause the pipeline to need to wait for
   * four memory loads. Instead, the items are uniformly distributed to blocks, and each counter is
   * uniformly selected from a distinct 16-byte segment. While the runtime memory layout may result
   * in the blocks not being cache-aligned, the L2 spatial prefetcher tries to load aligned pairs of
   * cache lines, so the typical cost is only one memory access.
   *
   * The frequency of all entries is aged periodically using a sampling window based on the maximum
   * number of entries in the cache. This is referred to as the reset operation by TinyLfu and keeps
   * the sketch fresh by dividing all counters by two and subtracting based on the number of odd
   * counters found. The O(n) cost of aging is amortized, ideal for hardware prefetching, and uses
   * inexpensive bit manipulations per array location.
   *
   * [1] An Improved Data Stream Summary: The Count-Min Sketch and its Applications
   * http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
   * [2] TinyLFU: A Highly Efficient Cache Admission Policy
   * https://dl.acm.org/citation.cfm?id=3149371
   * [3] Hash Function Prospector: Three round functions
   * https://github.com/skeeto/hash-prospector#three-round-functions
   */
        const val RESET_MASK: Long = 0x7777777777777777L
        const val ONE_MASK: Long = 0x1111111111111111L

        /** Applies a supplemental hash function to defend against a poor quality hash.  */
        fun spread( x: Int): Int {
            var x = x
            x = x xor (x ushr 17)
            x *= -0x12a52b45
            x = x xor (x ushr 11)
            x *= -0x53b3e4af
            x = x xor (x ushr 15)
            return x
        }

        /** Applies another round of hashing for additional randomization.  */
        fun rehash( x: Int): Int {
            var x = x
            x *= 0x31848bab
            x = x xor (x ushr 14)
            return x
        }
    }
}
